10036 - Divisibility/10036.cpp

   1 /*
   2   Accepted
   3  */
   4 #include <iostream>
   5
   6 using namespace std;
   7
   8 const int MAXN = 10000, MAXK = 100;
   9
  10 bool dp[MAXN][MAXK];
  11
  12 int main(){
  13   int cases;
  14   cin >> cases;
  15   while (cases--){
  16     int n, k;
  17     cin >> n >> k;
  18     if ( (0 <= n && n <= MAXN && 0 <= k && k <= MAXK) == false ) while (1);
  19     int a[n];
  20     for (int i=0; i<n; ++i){
  21       for (int j=0; j<k; ++j){
  22         dp[i][j] = false;
  23       }
  24       cin >> a[i];
  25     }
  26
  27     dp[0][abs(a[0])%k] = true;
  28     for (int i=0; i<n-1; ++i){
  29       for (int j=0; j<k; ++j){
  30         if (dp[i][j]){
  31           int t = j + a[i+1];
  32           while (t < 0) t += k;
  33           dp[i+1][t%k] = true;
  34
  35           t = j - a[i+1];
  36           while (t < 0) t += k;
  37           dp[i+1][t%k] = true;
  38         }
  39       }
  40     }
  41
  42     cout << (dp[n-1][0]?"D":"Not d") << "ivisible" << endl;
  43   }
  44   return 0;
  45 }